1. Field of Invention
The present invention relates to motion estimation, and particularly to a motion estimation circuit having a systolic array architecture and the operating method thereof.
2. Description of the Related Art
In general, the data amount of digital video is tremendously huge. To save the space for storing video data and the transmission bandwidth during transmitting video data, a video data compression must be implemented. To achieve the goal of reducing data, redundant information in a video data needs to be removed. For example, if a previous picture (or a “frame”) is similar with the next frame, the previous frame can be kept and the same contents in the next frame are removed; i.e. only the different information is kept. In this way, the data amount of a digital video is able to be significantly reduced. For instance, MPEG video compression standard is one of the most useful video encoding methods.
FIG. 1 is a schematic diagram briefly showing motion estimation operation for a normal video compression. Referring to FIG. 1, to compare a current frame CF with a previous frame PF, the current frame CF is normally divided into a plurality of image blocks (the image block PM in the figure is one of them). A typical size of an image block is 16×16 pixels or 8×8 pixels. Then, an image block PM (called “current image block”, even briefly “current block”) is one-by-one selected from the current frame and searched a most similar image block in the PF. To conduct the search, a search window in the PF should be defined; that is, in the PF a same-sized block PS is taken as a central point at a same position corresponding to the position of the image block PM in the current frame CF, and from the block PS extends a square area with a predetermined distance n at four sides is chosen as the search window. The above-mentioned predetermined distance is the search range. In the search window, an image block same-sized as the current image block PM is arbitrarily chosen (for example, the block PS is one of them) and a matching operation between the current image block PM and the chosen block is conducted for finding out the most similar image block. Such scheme is termed as motion estimation.
Generally, an SAD (sum of absolute difference) of pixel-to-pixel is calculated when comparing a current image block with a reference image block. In other words, all pixel data in the current image block are subtracted from the corresponded pixel data of the reference image block to obtain every difference of all pixels, followed by taking the absolute values thereof and doing summation of all absolute values. An SAD between the current image block and the reference block is obtained hereto. Whether the current image block and the reference image block are similar can be determined by the SAD value.
Since the motion estimation arbitrarily chooses a block same-sized as the current image block in the search window and a plurality of the chosen blocks is one-by-one compared with the current image block, it is obvious that the amount of the computation (or the computation time) thereof is tremendously large. On the other hand, a motion estimation circuit to efficiently meet such large computation is considerably complicated.
In particular, the newly revised standard H.264 has added image blocks with sizes of 8×16 pixels, 16×8 pixels, 8×4 pixels, 4×8 pixels and 4×4 pixels; the conventional technique fails to simultaneously compute SADs for image blocks with different sizes. Furthermore, the conventional technique is only capable computing individually image blocks with 16×16 pixels or 8×8 pixels and fails to support motion estimation in the form of a tree structure.